package class16;

/**
 * 面试常见的图数据，转成MyGraph结构
 */
public class GraphToMyGraph {

    // Matrix 是一个 N*3 的矩阵，每一个数据含义是 [weight, from ,to]，转换成MyGraph数据格式
    public static MyGraph.Graph<Integer> createGraph(int[][] matrix) {
        MyGraph.Graph<Integer> graph = new MyGraph.Graph<>();  // MyGraph图结构
        for (int[] data : matrix) {  // 遍历矩阵中的每一条边
            int weight = data[0];  // 记录下weight权重
            int from = data[1];  // 记录下from编号
            int to = data[2];  // 记录下to编号
            // 如果图中还没有from编号的结点，那么就创建from编号的结点
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new MyGraph.Node<>(from));
            }
            // 如果图中还没有to编号的结点，那么就创建to编号的结点
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new MyGraph.Node<>(to));
            }
            // 创建完后，拿到fromNode与toNode
            MyGraph.Node<Integer> fromNode = graph.nodes.get(from);
            MyGraph.Node<Integer> toNode = graph.nodes.get(to);
            // 新建一条边
            MyGraph.Edge<Integer> newEdge = new MyGraph.Edge<>(weight, fromNode, toNode);
            // 将两点与边关联起来
            fromNode.nexts.add(toNode);  // fromNode的有向边指向的邻居就是toNode，记录下来
            fromNode.out++;  // fromNode出度加1
            toNode.in++;  // toNode入度就得加1
            fromNode.edges.add(newEdge);  // fromNode有向边就多了一条
            graph.edges.add(newEdge);  // 整个图中多了一条边，记录下来
        }
        return graph;
    }

}
